八皇后問題可以說是一道相當經典的演算法題目，以西洋棋為背景，如何在一個8x8的棋盤上擺放八個皇后的棋子，讓任何一個皇后無法吃掉其中一個皇后，也是就是任何一個皇后的橫行、縱行、斜線上都不會出現其它的皇后，後來八皇后問題也被衍生為N皇后問題 - 在N*N的棋盤上放置N個皇后，試問有幾種解法?就讓我們用回溯法來解N皇后的問題吧!

圖片來源:https://medium.com/nerd-for-tech/genetic-algorithm-8-queens-problem-b01730e673fd

先用四皇后來推演一下流程

1. 假設現在有個4*4的棋盤，我們先將第一個皇后放在第一個格子裡面
   

2. 由於一個直行只能有一個皇后，所以接下來將第二個皇后放在第二行的第一個，不過因為皇后的橫列不可以有其它皇后，所以往下挪動一格
   

3. 真不巧，斜線上也不能出現其它皇后，因此要再往下挪動一格
   

4. 因此第二個皇后擺放在這個位置
   

5. 接下來放置第三個皇后，但會發現一個問題，不管放在哪個位置都不行，因次要使用回溯法來調整第二個皇后的位置，把他往下移動一格
   

6. 調整完之後第三個皇后也放好了
   

7. 不過在擺放第四個皇后的時候，又發生了一樣的問題，只好用回溯法再次倒回去
   

8. 重覆先前的步驟之後，總算能夠成功擺放四個皇后了!
   

用js實作

const NQueens = (n) => {
    let answer = 0;
    let arr = [];
    for (let i = 0; i < n; i++) {
        arr.push(Array.from({ length: n }).fill(null));
    }

    let i = 0; //第幾列(橫向)
    let j = 0; //第幾行(直向)
    let loop = true;
    while (loop) {
        console.log("i", i, "j", j);
        arr[i][j] = "Q";
        console.log("arr", arr);
        //檢查橫行、縱行、斜線是否有其它Q的flag
        let checkQExist = false;
        let k = 0;
        while (k < i) {
            //確認當前的Q上方是否有其它Q的存在
            if (arr[k][j] === "Q") {
                checkQExist = true;
            }
            k++;
        }
        k = 0;
        while (k < j) {
            //確認當前的Q左邊是否有其它Q的存在
            if (arr[i][k] === "Q") {
                checkQExist = true;
            }
            k++;
        }
        k = 1;
        let l = -1;
        while (i + k < n && j + l >= 0) {
            //確認當前的Q對角線(左下角)是否有其它Q的存在
            if (arr[i + k][j + l] === "Q") {
                checkQExist = true;
            }
            k++;
            l--;
        }
        k = -1;
        while (i + k >= 0 && j + k >= 0) {
            //確認當前的Q對角線(右上角)是否有其它Q的存在
            if (arr[i + k][j + k] === "Q") {
                checkQExist = true;
            }
            k--;
        }
        if (!checkQExist) {
            console.log("Q can put here");
            console.log(arr);
            //已經放到最後一行了
            if (j === n - 1) {
                answer++;
                console.log("perfect solution");
                console.log(arr);
                arr[i][j] = null;
                i++; //往下一列
            } else {
                //往下一行
                i = 0;
                j++;
            }
        }

        if (checkQExist) {
            console.log("Q exist!!");
            console.log(arr);
            arr[i][j] = null; //不能放這格所以要清空
            i++;
        }

        //檢查是否超出邊界
        const checkBoundary = () => {
            j--;
            for (let r = 0; r < arr.length; r++) {
                if (arr[r][j] === "Q") {
                    arr[r][j] = null;
                    console.log("r and j is", r, j);
                    i = r + 1;
                    break;
                }
            }
        };

        while (i >= n) {
            //如果橫列超過n 需檢查前一行
            checkBoundary();
            if (j < 0) {
                console.log("done");
                loop = false;
                break;
            }
        }
    }
    console.log("Number of solution", answer);
};

NQueens(4); //2

單看程式碼實在是過於抽象，為了幫助理解所以將陣列印出來看，就會比較清楚整體的運作流程為何

為了驗證程式碼是否正確，將input改為8，結果運算時間出乎我的意料，真的是所謂的讓子彈飛一會，非常的耗時，一度還讓我以為是否寫了無窮迴圈，還好最後成功印出92

維基百科提供的N皇后解答